package cn.leonis.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Author Tobi
 * @Date 2021-09-04 下午2:32
 * 多数元素
 */
public class MajorityElementSolution {

    public static void main(String[] args) {
        int[] nums = {3, 2, 3};
        MajorityElementSolution solution = new MajorityElementSolution();
        System.out.println(solution.majorityElement(nums));
    }

    /**
     * 解法一： 排序法，因为总是存在一个多数元素，排序完的中间元素必定是多数的那个元素，
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 解法二：位运算
     * @param nums
     * @return
     */
    public int majorityElement1(int[] nums) {
        

        return -1;
    }

    /**
     * 使用hashmap存储出现的次数，当超过n/2的时候，返回
     * @param nums
     * @return
     */
    public int majorityElement2(int[] nums) {
        Map<Integer, Integer> temp = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int count = temp.getOrDefault(nums[i], 0) + 1;
            if (count > nums.length / 2) {
                return nums[i];
            }
            temp.put(nums[i], count);
        }

        return -1;
    }

    /**
     * 摩尔投票法
     * @param nums
     * @return
     */
    public int majorityElement3(int[] nums) {
        int major = nums[0];
        int count = 1;
        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                count++;
                major = nums[i];
            } else if (major == nums[i]) {
                count++;
            }else {
                count--;
            }
        }

        return major;
    }
}
